#-*- coding: utf-8 -*-
'''from time import clock'''
import time
import random 
import matplotlib.pyplot as plt
import numpy
import math
import sys
from bsort import bubblesort
from qsort import quicksort
from iSort import insertionSort
from mSort import merge
from heapi import heapsort
from fstat import create



def calculo(algoritmo,tamanho):
	'''
	Funcao que cria as listas de valores e calculos do tempos da execucao dos algoritmos

	Parametros de entrada 
		algoritmo -> Opcao escolhida
		tamanho -> tamaanho maximpo para o array 

	Parametros de retorno 
		timeList -> lista de tempos da execucao do algoritmo
		rangeFor1 -> lista de n de elementos 
	'''
	timeList = [] 									# Lista de tempos
	timeListTemp = [] 								# Lista de tempos dos tempos do mesmo array
	desvioPad = [] 									# Lista de calculos do desvio padrao
	media=0
	rangeFor1 = range(50,tamanho,50) 				# n de valores dos arrays
	rangeFor2 = range(1,31,1) 						# n repeticoes para o mesmo array (array com os mesmos nr de elementos)
	
	for o in rangeFor1:								# for que incrementa os nr de valores em cada array
		print "n =", o
		X=numpy.random.randn(o) 					# Array ramdom
		T= list(X) 									# copia do array ramdom
		
		for a in rangeFor2:							# for que que calcula n vezes o tempo de ordenacao para um determinado array
			if algoritmo == 1:						# verifica se foi o algoritmo 1 que o utilizador escolheu
				execucao1= time.clock()				# tempo 1
				bubblesort(T)						# chamda da funcao do Bubble-Sort
				execucao2= time.clock()				# tempo 2
				T= list(X)							# Volta a copiar o array ramdom para poder voltar a ordenar 
			elif algoritmo == 2:					# verifica se foi o algoritmo 2 que o utilizador escolheu
				execucao1= time.clock()				# tempo 1
				quicksort(T,0,len(T)-1)				# chamda da funcao do Quicksort
				execucao2= time.clock()				# tempo 2
				T= list(X)							# Volta a copiar o array ramdom para poder voltar a ordenar 
			elif algoritmo == 3:					# verifica se foi o algoritmo 3 que o utilizador escolheu
				execucao1= time.clock()				# tempo 1
				insertionSort(T)					# chamda da funcao do Insertion-sort
				execucao2= time.clock()				# tempo 2
				T= list(X)							# Volta a copiar o array ramdom para poder voltar a ordenar 
			elif algoritmo == 4:					# verifica se foi o algoritmo 4 que o utilizador escolheu
				execucao1= time.clock()				# tempo 1
				merge(T,0,len(T)//2,len(T)-1)		# chamda da funcao do Merge Sort
				execucao2= time.clock()				# tempo 2
				T= list(X)							# Volta a copiar o array ramdom para poder voltar a ordenar 
			elif algoritmo == 5:					# verifica se foi o algoritmo 5 que o utilizador escolheu
				T.insert(0, sys.maxint)				# adiciona uma posicao antes de todas as outras para se poder conseguir usar o algoritmo
				execucao1= time.clock()				# tempo 1
				heapsort(T)							# chamda da funcao do Heapsort
				execucao2= time.clock()				# tempo 2
				T.pop(0)							# remove posicao anteriormente criada
				T= list(X)							# Volta a copiar o array ramdom para poder voltar a ordenar 

			totalTime=execucao2-execucao1			# calcula o tempo de execução do algoritmo
			media +=totalTime						# faz a soma de todos os tempos (para calcular a media)
			
			timeListTemp.append(totalTime)			# adiciona o n de tempos calculados para o mesmo nr de 
			
		pass
		media=media/len(rangeFor2)					# calcula a media
		timeList.append(media)						# adiciona a os resultados da media ao array que sera usado para mostrar o garfico
		
		desvioPad.append(calculoDesvio(media, timeListTemp))	# chama a funcao que calcula o DP e coloca o valor no array
		
		timeListTemp=[]								# limpa o array temporario
		
		media=0										
	pass
	create(algoritmo,rangeFor1,timeList,desvioPad)	#chama a funcao que cria o o ficheiro ods
	print "TEMPOS", timeList
	print "DESVIO PADRAO", desvioPad				# mostra o desvio padrao de cada n elementos do array
	return timeList, rangeFor1
pass


def calculoDesvio(media, timeListTemp):
	'''
	Funcao que calcula o Desvio Padrao 

	Parametros de entrada 
		media -> Media dos valores calculados n vezes para o mesmo array
		timeListTemp -> Array com os valores calculados n vezes para o mesmo array

	Parametros de retorno 
		desvio -> timeListTemp

	'''	
	temp=0
	for i in range(0, len(timeListTemp),1): 
		temp += (timeListTemp[i]-media)**2			# primeira parte da formula do DP
	pass
	desvio = math.sqrt(temp/(len(timeListTemp)-1))	# segunda parte da formula do DP
	return desvio
pass





def verifica(algoritmo,tamanho):
	'''
	Funcao que verifica se e para fazer o calculo de um so algoritmo ou de todos os algoritmos

	Parametros de entrada 
		algoritmo -> Opcao escolhida 
		tamanho -> tamaanho maximpo para o array 

	'''
	if algoritmo==10: 											# escolha total
		global flag 
		flag=1
		arryarry =[]
		for k in range(0,5,1):									# corre todos os algoritmos disponiveis na aplicacao
			timeList, rangeFor = calculo(k+1,tamanho) 			# chama funcao de calculo e grava os array retornados
			arryarry.append(timeList)							# adiciona os arrays retornados num array
		pass
		drawGraphic2(arryarry, rangeFor, len(rangeFor))			# chama a funca que desenha todos os graficos
	else:														# escolha singular 
		timeList, rangeFor =calculo(algoritmo,tamanho)			# chama funcao de calculo e grava os array retornados
		if algoritmo ==1 or algoritmo ==2 or algoritmo ==3: 	# verifica que formula do calculo teorico sera usado
			pteorList = [n**2 * (timeList[len(timeList) - 1] / rangeFor[len(rangeFor) -1]**2) for n in rangeFor]
		else:
			pteorList = [n*math.log(n,2) / ((rangeFor[len(rangeFor)-1])*math.log(rangeFor[len(rangeFor)-1]))*(timeList[len(timeList) - 1]) for n in rangeFor]
		pass
		drawGraphic(timeList,pteorList, rangeFor, len(rangeFor))
	pass
pass



def drawGraphic2(arryarry, nElement, ntotal):
	'''
	Funcao que desenha os gaficos dos tempos dos algoritmos todos 

	Parametros de entrada 
		arryarry -> Array com os array de tempos de cada algoritmo
		nElement -> Total de elementos de cada array de tempos 
		ntotal -> valor de vezes incrementado o for de posicoes do array para ordenacao
	'''
	plt.plot(nElement, arryarry[0], label="BubbleSort")
	plt.plot(nElement, arryarry[1], label="QuickSort")
	plt.plot(nElement, arryarry[2], label="InsertionSort")
	plt.plot(nElement, arryarry[3], label="MergeSort")
	plt.plot(nElement, arryarry[4], label="HeapSort")
	#plt.axis([-1, (ntotal* 50)+50, 0, 0.2])
	plt.grid(True)
	plt.legend()
	plt.show()
pass



def drawGraphic(timeList, pteorList, nElement, ntotal): 
	'''
	Funcao que desenha o gafico dos tempos e da previsao teorica do algoritmo desejado  

	Parametros de entrada 
		timeList -> Array com os tempos do algoritmo
		pteorList -> Array com os valores da previsao teorica
		nElement -> Total de elementos de cada array de tempos 
		ntotal -> valor de vezes incrementado o for de posicoes do array para ordenacao
	'''
	plt.plot(nElement, timeList,'bo', label="resultado experimental")
	plt.plot(nElement, pteorList, 'r^', label=u"previsão teórica")
	plt.axis([-1, (ntotal* 50)+100, 0, 0.2])
	plt.grid(True)
	plt.ylabel(u'T(n) - tempo de execução médio em segundos')
	plt.xlabel(u'n - número de elementos por array')
	plt.legend()
	plt.show()
pass


'''
MAIN
'''
print"\n Projeco Estruturas de Dados e Algoritmos"
print ('\n  1-> BubbleSort \n  2-> QuickSort \n  3-> InsertionSort \n  4-> MergeSort \n  5-> HeapSort \n  10-> todos')
algoritmo =input('\n Indique qual o algoritmo de ordenacao que deseja analizar:')
print "\n Indique o mumero maximo(multiplos de 50) de posicoes do array"
tamanho =input('\n que ira ser ordenado :')+50
	 
verifica(algoritmo,tamanho)

